package 算法.力扣;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author: 谢君臣
 * @create: 2020-09-01 22:18
 * @founction: XXXX
 */
public class leetcode {
    public static void main(String[] args) {
//        int[] nums = {2, 7, 11, 15};
//        int target = 18;
//        int[] ints = twoSum(nums, target);
//        System.out.println(Arrays.toString(ints));
//        System.out.println(lengthOfLongestSubstring("dvsgfs"));
//        sleetcode3("dvsgfs");
//        int[] x = {1, 0, 9};
//        int[] y = {5, 7, 8};
//        ListNode l1, l2;
//        ListNode l = new ListNode(9);
//        ListNode s = new ListNode(8);
//        for (int i = x.length - 2; i >= 0; i--) {
//            l1 = l;
//            l2 = s;
//            l = new ListNode(x[i]);
//            l.next = l1;
//            s = new ListNode(y[i]);
//            s.next = l2;
//        }
//        addTwoNumbers(l, s);
//        String s = longestPalindrome("cbbd");
//        System.out.println(s);
//        System.out.println(maxArea());
//        Solution();

    }

    /**
     * 将余数放入map中，当遇到value = key 则匹配成功。
     */
    public static int[] twoSum(int[] nums, int target) {
        int[] index = new int[2];
        /**
         * 建立k-v ，一一对应的哈希表
         * 将余数放入map中，当遇到value = key 则匹配成功。
         */
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (hash.containsKey(nums[i])) {
                index[0] = i;
                index[1] = hash.get(nums[i]);
                return index;
            }
            // 将数据存入 key为补数 ，value为下标
            hash.put(target - nums[i], i);
        }
        return index;
    }

    public static int lengthOfLongestSubstring(String s) {
        final int max = 0;
        return run(s, 0, 0);
    }

    public static int run(String s, int i, int max) {
        int length = i;
        char[] str = s.toCharArray();
        HashMap<Character, Integer> hash = new HashMap<Character, Integer>();
        for (int j = 0; j < i; j++)
            hash.put(str[j], j);
        for (; i < str.length; i++) {
            if (hash.containsKey(str[i])) {
                int start = hash.get(str[i]);  // 获取重复元素的下标
                int length1 = run(s.substring(start + 1, s.length()), i - start - 1, length);
                length = length1 > length ? length1 : length;
                break;
            } else {
                hash.put(str[i], i);
                length++;
            }
        }
        return length;
    }

    static int sleetcode3(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for (int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for (int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode head1 = head;
        int s = 0, y = 0; //商 余数
        while (l1 != null && l2 != null) {
            int i = l1.val + l2.val + s;
            y = i % 10;
            ListNode end = new ListNode(y);
            head1.next = end;
            head1 = head1.next;
            s = i / 10;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            int i = l1.val + s;
            y = i % 10;
            ListNode end = new ListNode(y);
            head1.next = end;
            head1 = head1.next;
            s = i / 10;
            l1 = l1.next;
        }
        while (l2 != null) {
            int i = l2.val + s;
            y = i % 10;
            ListNode end = new ListNode(y);
            head1.next = end;
            head1 = head1.next;
            s = i / 10;
            l2 = l2.next;
        }
        if (s > 0) {
            ListNode end = new ListNode(s);
            head1.next = end;
        }
        head = head.next;
        return head;
    }

    static String L = "";
    static int max = 0;

    public static String longestPalindrome(String s) {
        Palindrome(s);
        return L;
    }

    public static void Palindrome(String s) {
        if (hw(s) && s.length() > max && L.length() < s.length() / 2) {
            {
                L = s;
                max = s.length();
            }
        } else {
            if (s.substring(0, s.length() - 1).length() > max)
                Palindrome(s.substring(0, s.length() - 1));
            if (s.substring(1).length() > max)
                Palindrome(s.substring(1));
        }
    }

    public static boolean hw(String s) {
        char[] str = s.toCharArray();
        int i = 0, j = s.length() / 2;
        boolean flag = true;
        while (i < j) {
            if (str[i] != str[s.length() - 1 - i]) {
                flag = false;
                break;
            }
            i++;
        }
        return flag;
    }

    public static int maxArea() {
        int[] i = {76, 155, 15, 188, 180, 154, 84, 34, 187, 142, 22, 5, 27, 183, 111, 128, 50, 58, 2, 112, 179, 2, 100, 111, 115, 76, 134, 120, 118, 103, 31, 146, 58, 198, 134, 38, 104, 170, 25, 92, 112, 199, 49, 140, 135, 160, 20, 185, 171, 23, 98, 150, 177, 198, 61, 92, 26, 147, 164, 144, 51, 196, 42, 109, 194, 177, 100, 99, 99, 125, 143, 12, 76, 192, 152, 11, 152, 124, 197, 123, 147, 95, 73, 124, 45, 86, 168, 24, 34, 133, 120, 85, 81, 163, 146, 75, 92, 198, 126, 191};
        sumarea(i);
        return max;
    }

    public static void sumarea(int[] height) {
        int sum = Math.min(height[0], height[height.length - 1]) * (height.length - 1);
        if (sum > max)
            max = sum;
        if (height.length >= 3) {
            int[] head = Arrays.copyOf(height, height.length - 1);
            int[] end = Arrays.copyOfRange(height, 1, height.length);
            if (head.length > 1 && Arrays.stream(head).max().getAsInt() * (head.length - 1) > max)
                sumarea(head);
            if (end.length > 1 && Arrays.stream(end).max().getAsInt() * (end.length - 1) > max)
                sumarea(end);
        }
    }
    public int maxArea(int[] height) {
        int len = height.length;
        if (len < 2) {
            return 0;
        }
        int left = 0;
        int right = len - 1;
        int res = 0;
        while (left < right) {
            int minHeight = Math.min(height[left], height[right]);
            res = Math.max(res, minHeight * (right - left));
            int[] curr = Arrays.copyOfRange(height, left, right+1);
            if ( Arrays.stream(curr).max().getAsInt() * (curr.length - 1) < res)
                break;
            if (height[left] == minHeight) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }

}
class sadf {
    public boolean exist(char[][] board, String word) {
        if (word==null) return true;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i=0;i<board.length;i++) {
            for (int j=0;j<board[0].length;j++) {
                if (board[i][j]==word.charAt(0) && this.search(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean search(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        if (index>=word.length()) return true;
        if (i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=word.charAt(index) || visited[i][j]) {
            return false;
        }
        visited[i][j] = true;
        if (this.search(board,word,i-1,j,index+1,visited) ||
                this.search(board,word,i,j+1,index+1,visited) ||
                this.search(board,word,i+1,j,index+1,visited) ||
                this.search(board,word,i,j-1,index+1,visited) )
            return true;
        visited[i][j] = false;
        return false;
    }
}
